{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Word Search II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #array #string #backtracking #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #数组 #字符串 #回溯 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findWords"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #单词搜索 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个&nbsp;<code>m x n</code> 二维字符网格&nbsp;<code>board</code><strong>&nbsp;</strong>和一个单词（字符串）列表 <code>words</code>，&nbsp;<em>返回所有二维网格上的单词</em>&nbsp;。</p>\n",
    "\n",
    "<p>单词必须按照字母顺序，通过 <strong>相邻的单元格</strong> 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/07/search1.jpg\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [[\"o\",\"a\",\"a\",\"n\"],[\"e\",\"t\",\"a\",\"e\"],[\"i\",\"h\",\"k\",\"r\"],[\"i\",\"f\",\"l\",\"v\"]], words = [\"oath\",\"pea\",\"eat\",\"rain\"]\n",
    "<strong>输出：</strong>[\"eat\",\"oath\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/07/search2.jpg\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [[\"a\",\"b\"],[\"c\",\"d\"]], words = [\"abcb\"]\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == board.length</code></li>\n",
    "\t<li><code>n == board[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 12</code></li>\n",
    "\t<li><code>board[i][j]</code> 是一个小写英文字母</li>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 10</code></li>\n",
    "\t<li><code>words[i]</code> 由小写英文字母组成</li>\n",
    "\t<li><code>words</code> 中的所有字符串互不相同</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [word-search-ii](https://leetcode.cn/problems/word-search-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [word-search-ii](https://leetcode.cn/problems/word-search-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"o\",\"a\",\"a\",\"n\"],[\"e\",\"t\",\"a\",\"e\"],[\"i\",\"h\",\"k\",\"r\"],[\"i\",\"f\",\"l\",\"v\"]]\\n[\"oath\",\"pea\",\"eat\",\"rain\"]', '[[\"a\",\"b\"],[\"c\",\"d\"]]\\n[\"abcb\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found words: ['oath', 'nerkl', 'eat', 'iflv']\n"
     ]
    }
   ],
   "source": [
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.WORD_KEY = '$'\n",
    "        self.trie = {}\n",
    "        self.board = None\n",
    "        self.result = []\n",
    "\n",
    "    def build_trie(self, words: List[str]):\n",
    "        \"\"\"构建字典树用于存储单词列表\"\"\"\n",
    "        for word in words:\n",
    "            node = self.trie\n",
    "            for letter in word:\n",
    "                node = node.setdefault(letter, {})\n",
    "            node[self.WORD_KEY] = word\n",
    "\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        \"\"\"在给定的字符网格中查找单词列表\"\"\"\n",
    "        self.board = board\n",
    "        self.build_trie(words)\n",
    "\n",
    "        for row in range(len(board)):\n",
    "            for col in range(len(board[0])):\n",
    "                if board[row][col] in self.trie:\n",
    "                    self.backtracking(row, col, self.trie)\n",
    "        return self.result\n",
    "\n",
    "    def backtracking(self, row: int, col: int, parent: dict):\n",
    "        \"\"\"使用回溯法在网格中搜索字典树中的单词\"\"\"\n",
    "        letter = self.board[row][col]\n",
    "        currNode = parent[letter]\n",
    "\n",
    "        word_match = currNode.pop(self.WORD_KEY, False)\n",
    "        if word_match:\n",
    "            self.result.append(word_match)\n",
    "\n",
    "        self.board[row][col] = '#'\n",
    "        for rowOffset, colOffset in [(-1, 0), (0, 1), (1, 0), (0, -1)]:\n",
    "            newRow, newCol = row + rowOffset, col + colOffset\n",
    "            if 0 <= newRow < len(self.board) and 0 <= newCol < len(self.board[0]):\n",
    "                if self.board[newRow][newCol] in currNode:\n",
    "                    self.backtracking(newRow, newCol, currNode)\n",
    "\n",
    "        self.board[row][col] = letter\n",
    "        if not currNode:\n",
    "            parent.pop(letter)\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    board = [\n",
    "        ['o','a','a','n'],\n",
    "        ['e','t','a','e'],\n",
    "        ['i','h','k','r'],\n",
    "        ['i','f','l','v']\n",
    "    ]\n",
    "    words = [\"oath\", \"pea\", \"eat\", \"rain\", 'iflv', 'nerkl']\n",
    "\n",
    "    solution = Solution()\n",
    "    found_words = solution.findWords(board, words)\n",
    "    print(\"Found words:\", found_words)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "DEBUG:root:函数：trace_function_stack, 局部变量：{'stack': [FrameInfo(frame=<frame at 0x000001FB6B1841D8, file 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Local\\\\Temp\\\\ipykernel_3152\\\\2474690752.py', line 12, code trace_function_stack>, filename='C:\\\\Users\\\\Administrator\\\\AppData\\\\Local\\\\Temp\\\\ipykernel_3152\\\\2474690752.py', lineno=7, function='trace_function_stack', code_context=['    stack = inspect.stack()\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB69CF3858, file 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Local\\\\Temp\\\\ipykernel_3152\\\\2474690752.py', line 15, code some_function>, filename='C:\\\\Users\\\\Administrator\\\\AppData\\\\Local\\\\Temp\\\\ipykernel_3152\\\\2474690752.py', lineno=15, function='some_function', code_context=['    trace_function_stack()\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB69F9B408, file 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Local\\\\Temp\\\\ipykernel_3152\\\\2474690752.py', line 18, code <module>>, filename='C:\\\\Users\\\\Administrator\\\\AppData\\\\Local\\\\Temp\\\\ipykernel_3152\\\\2474690752.py', lineno=18, function='<module>', code_context=['some_function(5, 7)\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB6A1552F8, file 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\IPython\\\\core\\\\interactiveshell.py', line 3553, code run_code>, filename='C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\IPython\\\\core\\\\interactiveshell.py', lineno=3553, function='run_code', code_context=['                    exec(code_obj, self.user_global_ns, self.user_ns)\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB69BF8718, file 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\IPython\\\\core\\\\interactiveshell.py', line 3473, code run_ast_nodes>, filename='C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\IPython\\\\core\\\\interactiveshell.py', lineno=3473, function='run_ast_nodes', code_context=['                    if (await self.run_code(code, result,  async_=asy)):\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB69C13498, file 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\IPython\\\\core\\\\interactiveshell.py', line 3258, code run_cell_async>, filename='C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\IPython\\\\core\\\\interactiveshell.py', lineno=3258, function='run_cell_async', code_context=['                       interactivity=interactivity, compiler=compiler, result=result)\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB6AFAB230, file 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\IPython\\\\core\\\\async_helpers.py', line 78, code _pseudo_sync_runner>, filename='C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\IPython\\\\core\\\\async_helpers.py', lineno=78, function='_pseudo_sync_runner', code_context=['        coro.send(None)\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB69CAEC88, file 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\IPython\\\\core\\\\interactiveshell.py', line 3030, code _run_cell>, filename='C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\IPython\\\\core\\\\interactiveshell.py', lineno=3030, function='_run_cell', code_context=['            return runner(coro)\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB6A091658, file 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\IPython\\\\core\\\\interactiveshell.py', line 2976, code run_cell>, filename='C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\IPython\\\\core\\\\interactiveshell.py', lineno=2976, function='run_cell', code_context=['                raw_cell, store_history, silent, shell_futures, cell_id\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB6A092DF8, file 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel\\\\zmqshell.py', line 528, code run_cell>, filename='C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel\\\\zmqshell.py', lineno=528, function='run_cell', code_context=['        return super().run_cell(*args, **kwargs)\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB69E87F98, file 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel\\\\ipkernel.py', line 387, code do_execute>, filename='C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel\\\\ipkernel.py', lineno=387, function='do_execute', code_context=['                        cell_id=cell_id,\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB6A14C5E8, file 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel\\\\kernelbase.py', line 730, code execute_request>, filename='C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel\\\\kernelbase.py', lineno=730, function='execute_request', code_context=['            reply_content = await reply_content\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB6A08AF28, file 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel\\\\kernelbase.py', line 406, code dispatch_shell>, filename='C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel\\\\kernelbase.py', lineno=406, function='dispatch_shell', code_context=['                    await result\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB6AFA1630, file 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel\\\\kernelbase.py', line 499, code process_one>, filename='C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel\\\\kernelbase.py', lineno=499, function='process_one', code_context=['        await dispatch(*args)\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB6AF50CF8, file 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel\\\\kernelbase.py', line 510, code dispatch_queue>, filename='C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel\\\\kernelbase.py', lineno=510, function='dispatch_queue', code_context=['                await self.process_one()\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB6A186A08, file 'e:\\\\SoftwaresInstalled\\\\anaconda3\\\\lib\\\\asyncio\\\\events.py', line 88, code _run>, filename='e:\\\\SoftwaresInstalled\\\\anaconda3\\\\lib\\\\asyncio\\\\events.py', lineno=88, function='_run', code_context=['            self._context.run(self._callback, *self._args)\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB6B3A8068, file 'e:\\\\SoftwaresInstalled\\\\anaconda3\\\\lib\\\\asyncio\\\\base_events.py', line 1775, code _run_once>, filename='e:\\\\SoftwaresInstalled\\\\anaconda3\\\\lib\\\\asyncio\\\\base_events.py', lineno=1775, function='_run_once', code_context=['                handle._run()\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB6AF9EB88, file 'e:\\\\SoftwaresInstalled\\\\anaconda3\\\\lib\\\\asyncio\\\\base_events.py', line 539, code run_forever>, filename='e:\\\\SoftwaresInstalled\\\\anaconda3\\\\lib\\\\asyncio\\\\base_events.py', lineno=539, function='run_forever', code_context=['                self._run_once()\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB6AF9E9A8, file 'e:\\\\SoftwaresInstalled\\\\anaconda3\\\\lib\\\\site-packages\\\\tornado\\\\platform\\\\asyncio.py', line 215, code start>, filename='e:\\\\SoftwaresInstalled\\\\anaconda3\\\\lib\\\\site-packages\\\\tornado\\\\platform\\\\asyncio.py', lineno=215, function='start', code_context=['            self.asyncio_loop.run_forever()\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB6AEAB648, file 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel\\\\kernelapp.py', line 712, code start>, filename='C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel\\\\kernelapp.py', lineno=712, function='start', code_context=['                self.io_loop.start()\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB66A180B8, file 'e:\\\\SoftwaresInstalled\\\\anaconda3\\\\lib\\\\site-packages\\\\traitlets\\\\config\\\\application.py', line 976, code launch_instance>, filename='e:\\\\SoftwaresInstalled\\\\anaconda3\\\\lib\\\\site-packages\\\\traitlets\\\\config\\\\application.py', lineno=976, function='launch_instance', code_context=['        app.start()\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB6681F8E0, file 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel_launcher.py', line 17, code <module>>, filename='C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel_launcher.py', lineno=17, function='<module>', code_context=['    app.launch_new_instance()\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB6674A328, file 'e:\\\\SoftwaresInstalled\\\\anaconda3\\\\lib\\\\runpy.py', line 85, code _run_code>, filename='e:\\\\SoftwaresInstalled\\\\anaconda3\\\\lib\\\\runpy.py', lineno=85, function='_run_code', code_context=['    exec(code, run_globals)\\n'], index=0), FrameInfo(frame=<frame at 0x000001FB65DDA558, file 'e:\\\\SoftwaresInstalled\\\\anaconda3\\\\lib\\\\runpy.py', line 193, code _run_module_as_main>, filename='e:\\\\SoftwaresInstalled\\\\anaconda3\\\\lib\\\\runpy.py', lineno=193, function='_run_module_as_main', code_context=['                     \"__main__\", mod_spec)\\n'], index=0)], 'frame_info': FrameInfo(frame=<frame at 0x000001FB6B1841D8, file 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Local\\\\Temp\\\\ipykernel_3152\\\\2474690752.py', line 12, code trace_function_stack>, filename='C:\\\\Users\\\\Administrator\\\\AppData\\\\Local\\\\Temp\\\\ipykernel_3152\\\\2474690752.py', lineno=7, function='trace_function_stack', code_context=['    stack = inspect.stack()\\n'], index=0), 'function_name': 'trace_function_stack', 'frame': <frame at 0x000001FB6B1841D8, file 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Local\\\\Temp\\\\ipykernel_3152\\\\2474690752.py', line 12, code trace_function_stack>}\n",
      "DEBUG:root:函数：some_function, 局部变量：{'a': 5, 'b': 7}\n",
      "DEBUG:root:函数：<module>, 局部变量：{'__name__': '__main__', '__doc__': 'Automatically created module for IPython interactive environment', '__package__': None, '__loader__': None, '__spec__': None, '__builtin__': <module 'builtins' (built-in)>, '__builtins__': <module 'builtins' (built-in)>, '_ih': ['', 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)', 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)', 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)'], '_oh': {1: 12, 2: 12}, '_dh': ['f:\\\\gitee\\\\leetcode-automation\\\\leetcodeAutomation\\\\data\\\\notebook'], 'In': ['', 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)', 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)', 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)'], 'Out': {1: 12, 2: 12}, 'get_ipython': <bound method InteractiveShell.get_ipython of <ipykernel.zmqshell.ZMQInteractiveShell object at 0x000001FB6AEED828>>, 'exit': <IPython.core.autocall.ZMQExitAutocall object at 0x000001FB6AF55390>, 'quit': <IPython.core.autocall.ZMQExitAutocall object at 0x000001FB6AF55390>, '_': 12, '__': 12, '___': '', '__vsc_ipynb_file__': 'f:\\\\gitee\\\\leetcode-automation\\\\leetcodeAutomation\\\\data\\\\notebook\\\\word-search-ii.ipynb', 'builtins': <module 'builtins' (built-in)>, 'ipykernel': <module 'ipykernel' from 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel\\\\__init__.py'>, 'debugpy': <module 'debugpy' from 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\debugpy\\\\__init__.py'>, '_i': 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)', '_ii': 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)', '_iii': '', '_i1': 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)', 'inspect': <module 'inspect' from 'e:\\\\SoftwaresInstalled\\\\anaconda3\\\\lib\\\\inspect.py'>, 'logging': <module 'logging' from 'e:\\\\SoftwaresInstalled\\\\anaconda3\\\\lib\\\\logging\\\\__init__.py'>, 'trace_function_stack': <function trace_function_stack at 0x000001FB6D15F8C8>, 'some_function': <function some_function at 0x000001FB6D0F6950>, '_1': 12, 'file': 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Local\\\\Temp\\\\ipykernel_3152\\\\2943116772.py', '_i2': 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)', '_2': 12, '_i3': 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)'}\n",
      "DEBUG:root:函数：run_code, 局部变量：{'self': <ipykernel.zmqshell.ZMQInteractiveShell object at 0x000001FB6AEED828>, 'code_obj': <code object <module> at 0x000001FB6D0E4F60, file \"C:\\Users\\Administrator\\AppData\\Local\\Temp\\ipykernel_3152\\2474690752.py\", line 18>, 'result': <ExecutionResult object at 1fb6cda5400, execution_count=3 error_before_exec=None error_in_exec=None info=<ExecutionInfo object at 1fb6cda5b70, raw_cell=\"import inspect\n",
      "import logging\n",
      "\n",
      "logging.basicConfig..\" store_history=True silent=False shell_futures=True cell_id=vscode-notebook-cell:/f%3A/gitee/leetcode-automation/leetcodeAutomation/data/notebook/word-search-ii.ipynb#X64sZmlsZQ%3D%3D> result=None>, 'async_': False, '__tracebackhide__': '__ipython_bottom__', 'old_excepthook': <bound method IPKernelApp.excepthook of <ipykernel.kernelapp.IPKernelApp object at 0x000001FB66381CC0>>, 'outflag': True}\n",
      "DEBUG:root:函数：run_ast_nodes, 局部变量：{'self': <ipykernel.zmqshell.ZMQInteractiveShell object at 0x000001FB6AEED828>, 'nodelist': [<_ast.Import object at 0x000001FB6CDA5978>, <_ast.Import object at 0x000001FB6CDA5908>, <_ast.Expr object at 0x000001FB6CD76898>, <_ast.FunctionDef object at 0x000001FB6D127240>, <_ast.FunctionDef object at 0x000001FB6D127710>, <_ast.Expr object at 0x000001FB6D132588>], 'cell_name': 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Local\\\\Temp\\\\ipykernel_3152\\\\2474690752.py', 'interactivity': 'last', 'compiler': <ipykernel.compiler.XCachingCompiler object at 0x000001FB6AF18940>, 'result': <ExecutionResult object at 1fb6cda5400, execution_count=3 error_before_exec=None error_in_exec=None info=<ExecutionInfo object at 1fb6cda5b70, raw_cell=\"import inspect\n",
      "import logging\n",
      "\n",
      "logging.basicConfig..\" store_history=True silent=False shell_futures=True cell_id=vscode-notebook-cell:/f%3A/gitee/leetcode-automation/leetcodeAutomation/data/notebook/word-search-ii.ipynb#X64sZmlsZQ%3D%3D> result=None>, 'to_run_exec': [<_ast.Import object at 0x000001FB6CDA5978>, <_ast.Import object at 0x000001FB6CDA5908>, <_ast.Expr object at 0x000001FB6CD76898>, <_ast.FunctionDef object at 0x000001FB6D127240>, <_ast.FunctionDef object at 0x000001FB6D127710>], 'to_run_interactive': [<_ast.Expr object at 0x000001FB6D132588>], 'mod': <_ast.Interactive object at 0x000001FB6D1322B0>, 'compare': <function InteractiveShell.run_ast_nodes.<locals>.compare at 0x000001FB6D15F158>, 'to_run': [(<_ast.Import object at 0x000001FB6CDA5978>, 'exec'), (<_ast.Import object at 0x000001FB6CDA5908>, 'exec'), (<_ast.Expr object at 0x000001FB6CD76898>, 'exec'), (<_ast.FunctionDef object at 0x000001FB6D127240>, 'exec'), (<_ast.FunctionDef object at 0x000001FB6D127710>, 'exec'), (<_ast.Expr object at 0x000001FB6D132588>, 'single')], 'node': <_ast.Expr object at 0x000001FB6D132588>, 'mode': 'single', 'code': <code object <module> at 0x000001FB6D0E4F60, file \"C:\\Users\\Administrator\\AppData\\Local\\Temp\\ipykernel_3152\\2474690752.py\", line 18>, 'asy': False, '_async': False}\n",
      "DEBUG:root:函数：run_cell_async, 局部变量：{'raw_cell': 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)\\n', 'silent': False, 'shell_futures': True, 'transformed_cell': 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)\\n', 'preprocessing_exc_tuple': None, 'cell_id': 'vscode-notebook-cell:/f%3A/gitee/leetcode-automation/leetcodeAutomation/data/notebook/word-search-ii.ipynb#X64sZmlsZQ%3D%3D', 'info': <ExecutionInfo object at 1fb6cda5b70, raw_cell=\"import inspect\n",
      "import logging\n",
      "\n",
      "logging.basicConfig..\" store_history=True silent=False shell_futures=True cell_id=vscode-notebook-cell:/f%3A/gitee/leetcode-automation/leetcodeAutomation/data/notebook/word-search-ii.ipynb#X64sZmlsZQ%3D%3D>, 'error_before_exec': <function InteractiveShell.run_cell_async.<locals>.error_before_exec at 0x000001FB6D15F598>, 'cell': 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)\\n', 'compiler': <ipykernel.compiler.XCachingCompiler object at 0x000001FB6AF18940>, '_run_async': False, 'cell_name': 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Local\\\\Temp\\\\ipykernel_3152\\\\2474690752.py', 'code_ast': <_ast.Module object at 0x000001FB6CDA5B00>, 'interactivity': 'last_expr', 'result': <ExecutionResult object at 1fb6cda5400, execution_count=3 error_before_exec=None error_in_exec=None info=<ExecutionInfo object at 1fb6cda5b70, raw_cell=\"import inspect\n",
      "import logging\n",
      "\n",
      "logging.basicConfig..\" store_history=True silent=False shell_futures=True cell_id=vscode-notebook-cell:/f%3A/gitee/leetcode-automation/leetcodeAutomation/data/notebook/word-search-ii.ipynb#X64sZmlsZQ%3D%3D> result=None>, 'self': <ipykernel.zmqshell.ZMQInteractiveShell object at 0x000001FB6AEED828>, 'store_history': True}\n",
      "DEBUG:root:函数：_pseudo_sync_runner, 局部变量：{'coro': <coroutine object InteractiveShell.run_cell_async at 0x000001FB6D11B3C8>}\n",
      "DEBUG:root:函数：_run_cell, 局部变量：{'self': <ipykernel.zmqshell.ZMQInteractiveShell object at 0x000001FB6AEED828>, 'raw_cell': 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)\\n', 'store_history': True, 'silent': False, 'shell_futures': True, 'cell_id': 'vscode-notebook-cell:/f%3A/gitee/leetcode-automation/leetcodeAutomation/data/notebook/word-search-ii.ipynb#X64sZmlsZQ%3D%3D', 'preprocessing_exc_tuple': None, 'transformed_cell': 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)\\n', 'coro': <coroutine object InteractiveShell.run_cell_async at 0x000001FB6D11B3C8>, 'runner': <function _pseudo_sync_runner at 0x000001FB692EC730>}\n",
      "DEBUG:root:函数：run_cell, 局部变量：{'self': <ipykernel.zmqshell.ZMQInteractiveShell object at 0x000001FB6AEED828>, 'raw_cell': 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)\\n', 'store_history': True, 'silent': False, 'shell_futures': True, 'cell_id': 'vscode-notebook-cell:/f%3A/gitee/leetcode-automation/leetcodeAutomation/data/notebook/word-search-ii.ipynb#X64sZmlsZQ%3D%3D', 'result': None}\n",
      "DEBUG:root:函数：run_cell, 局部变量：{'self': <ipykernel.zmqshell.ZMQInteractiveShell object at 0x000001FB6AEED828>, 'args': ('import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)\\n',), 'kwargs': {'store_history': True, 'silent': False, 'cell_id': 'vscode-notebook-cell:/f%3A/gitee/leetcode-automation/leetcodeAutomation/data/notebook/word-search-ii.ipynb#X64sZmlsZQ%3D%3D'}, '__class__': <class 'ipykernel.zmqshell.ZMQInteractiveShell'>}\n",
      "DEBUG:root:函数：do_execute, 局部变量：{'self': <ipykernel.ipkernel.IPythonKernel object at 0x000001FB6AEED208>, 'code': 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)\\n', 'silent': False, 'store_history': True, 'user_expressions': {}, 'allow_stdin': True, 'cell_id': 'vscode-notebook-cell:/f%3A/gitee/leetcode-automation/leetcodeAutomation/data/notebook/word-search-ii.ipynb#X64sZmlsZQ%3D%3D', 'reply_content': {}, 'run_cell': <bound method InteractiveShell.run_cell_async of <ipykernel.zmqshell.ZMQInteractiveShell object at 0x000001FB6AEED828>>, 'should_run_async': <bound method InteractiveShell.should_run_async of <ipykernel.zmqshell.ZMQInteractiveShell object at 0x000001FB6AEED828>>, 'with_cell_id': True, 'preprocessing_exc_tuple': None, 'transformed_cell': 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)\\n', 'shell': <ipykernel.zmqshell.ZMQInteractiveShell object at 0x000001FB6AEED828>}\n",
      "DEBUG:root:函数：execute_request, 局部变量：{'self': <ipykernel.ipkernel.IPythonKernel object at 0x000001FB6AEED208>, 'stream': <zmq.eventloop.zmqstream.ZMQStream object at 0x000001FB6AF02860>, 'ident': [b'254816ef-1e2f-45fa-8707-5113e554db8b'], 'parent': {'header': {'date': datetime.datetime(2023, 12, 22, 9, 22, 35, 940000, tzinfo=tzutc()), 'msg_id': 'f06bebf9-bc9d-47ca-ad35-1ac4d764e962', 'msg_type': 'execute_request', 'session': '853d80b7-0aa3-4b1b-a8b8-19e44ca6eaa0', 'username': '922d2030-6134-4fa4-b328-0c1ffcc2679f', 'version': '5.2'}, 'msg_id': 'f06bebf9-bc9d-47ca-ad35-1ac4d764e962', 'msg_type': 'execute_request', 'parent_header': {}, 'metadata': {'cellId': 'vscode-notebook-cell:/f%3A/gitee/leetcode-automation/leetcodeAutomation/data/notebook/word-search-ii.ipynb#X64sZmlsZQ%3D%3D'}, 'content': {'silent': False, 'store_history': True, 'user_expressions': {}, 'allow_stdin': True, 'stop_on_error': False, 'code': 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)\\n'}, 'buffers': []}, 'content': {'silent': False, 'store_history': True, 'user_expressions': {}, 'allow_stdin': True, 'stop_on_error': False, 'code': 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)\\n'}, 'code': 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)\\n', 'silent': False, 'store_history': True, 'user_expressions': {}, 'allow_stdin': True, 'stop_on_error': False, 'metadata': {'started': datetime.datetime(2023, 12, 22, 9, 22, 35, 944269, tzinfo=datetime.timezone.utc), 'dependencies_met': True, 'engine': 'a6e1046c-3b91-4f85-99b7-32a08679b5c2'}, 'cell_id': 'vscode-notebook-cell:/f%3A/gitee/leetcode-automation/leetcodeAutomation/data/notebook/word-search-ii.ipynb#X64sZmlsZQ%3D%3D', 'reply_content': <coroutine object IPythonKernel.do_execute at 0x000001FB6AFA9248>}\n",
      "DEBUG:root:函数：dispatch_shell, 局部变量：{'self': <ipykernel.ipkernel.IPythonKernel object at 0x000001FB6AEED208>, 'msg': {'header': {'date': datetime.datetime(2023, 12, 22, 9, 22, 35, 940000, tzinfo=tzutc()), 'msg_id': 'f06bebf9-bc9d-47ca-ad35-1ac4d764e962', 'msg_type': 'execute_request', 'session': '853d80b7-0aa3-4b1b-a8b8-19e44ca6eaa0', 'username': '922d2030-6134-4fa4-b328-0c1ffcc2679f', 'version': '5.2'}, 'msg_id': 'f06bebf9-bc9d-47ca-ad35-1ac4d764e962', 'msg_type': 'execute_request', 'parent_header': {}, 'metadata': {'cellId': 'vscode-notebook-cell:/f%3A/gitee/leetcode-automation/leetcodeAutomation/data/notebook/word-search-ii.ipynb#X64sZmlsZQ%3D%3D'}, 'content': {'silent': False, 'store_history': True, 'user_expressions': {}, 'allow_stdin': True, 'stop_on_error': False, 'code': 'import inspect\\nimport logging\\n\\nlogging.basicConfig(level=logging.DEBUG)\\n\\ndef trace_function_stack():\\n    stack = inspect.stack()\\n    for frame_info in stack:\\n        function_name = frame_info.function\\n        frame = frame_info.frame\\n        local_vars = frame.f_locals\\n        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\\n\\ndef some_function(a, b):\\n    trace_function_stack()\\n    return a + b\\n\\nsome_function(5, 7)\\n'}, 'buffers': []}, 'idents': [b'254816ef-1e2f-45fa-8707-5113e554db8b'], 'msg_type': 'execute_request', 'handler': <bound method Kernel.execute_request of <ipykernel.ipkernel.IPythonKernel object at 0x000001FB6AEED208>>, 'result': <coroutine object Kernel.execute_request at 0x000001FB6CD89448>}\n",
      "DEBUG:root:函数：process_one, 局部变量：{'self': <ipykernel.ipkernel.IPythonKernel object at 0x000001FB6AEED208>, 'wait': True, 't': 26, 'dispatch': <bound method Kernel.dispatch_shell of <ipykernel.ipkernel.IPythonKernel object at 0x000001FB6AEED208>>, 'args': ([<zmq.sugar.frame.Frame object at 0x000001FB6D174DF0>, <zmq.sugar.frame.Frame object at 0x000001FB6D174EA8>, <zmq.sugar.frame.Frame object at 0x000001FB6D174F60>, <zmq.sugar.frame.Frame object at 0x000001FB6D1749A0>, <zmq.sugar.frame.Frame object at 0x000001FB6D174A58>, <zmq.sugar.frame.Frame object at 0x000001FB6D174B10>, <zmq.sugar.frame.Frame object at 0x000001FB6D174BC8>],)}\n",
      "DEBUG:root:函数：dispatch_queue, 局部变量：{'self': <ipykernel.ipkernel.IPythonKernel object at 0x000001FB6AEED208>}\n",
      "DEBUG:root:函数：_run, 局部变量：{'self': <Handle <TaskWakeupMethWrapper object at 0x000001FB6D1027F8>(<Future finis...B10>, ...],))>)>}\n",
      "DEBUG:root:函数：_run_once, 局部变量：{'self': <_WindowsSelectorEventLoop running=True closed=False debug=False>, 'sched_count': 0, 'handle': <Handle <TaskWakeupMethWrapper object at 0x000001FB6D1027F8>(<Future finis...B10>, ...],))>)>, 'timeout': 0, 'event_list': [], 'end_time': 30768.827625, 'ntodo': 2, 'i': 0}\n",
      "DEBUG:root:函数：run_forever, 局部变量：{'self': <_WindowsSelectorEventLoop running=True closed=False debug=False>, 'old_agen_hooks': asyncgen_hooks(firstiter=None, finalizer=None)}\n",
      "DEBUG:root:函数：start, 局部变量：{'self': <tornado.platform.asyncio.AsyncIOMainLoop object at 0x000001FB6AF025F8>, 'old_loop': <_WindowsSelectorEventLoop running=True closed=False debug=False>}\n",
      "DEBUG:root:函数：start, 局部变量：{'self': <ipykernel.kernelapp.IPKernelApp object at 0x000001FB66381CC0>}\n",
      "DEBUG:root:函数：launch_instance, 局部变量：{'cls': <class 'ipykernel.kernelapp.IPKernelApp'>, 'argv': None, 'kwargs': {}, 'app': <ipykernel.kernelapp.IPKernelApp object at 0x000001FB66381CC0>}\n",
      "DEBUG:root:函数：<module>, 局部变量：{'__name__': '__main__', '__doc__': 'Entry point for launching an IPython kernel.\\n\\nThis is separate from the ipykernel package so we can avoid doing imports until\\nafter removing the cwd from sys.path.\\n', '__package__': '', '__loader__': <_frozen_importlib_external.SourceFileLoader object at 0x000001FB6685C630>, '__spec__': ModuleSpec(name='ipykernel_launcher', loader=<_frozen_importlib_external.SourceFileLoader object at 0x000001FB6685C630>, origin='C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel_launcher.py'), '__annotations__': {}, '__builtins__': <module 'builtins' (built-in)>, '__file__': 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel_launcher.py', '__cached__': 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\__pycache__\\\\ipykernel_launcher.cpython-37.pyc', 'sys': <module 'sys' (built-in)>, 'app': <module 'ipykernel.kernelapp' from 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel\\\\kernelapp.py'>}\n",
      "DEBUG:root:函数：_run_code, 局部变量：{'code': <code object <module> at 0x000001FB66848390, file \"C:\\Users\\Administrator\\AppData\\Roaming\\Python\\Python37\\site-packages\\ipykernel_launcher.py\", line 5>, 'run_globals': {'__name__': '__main__', '__doc__': 'Entry point for launching an IPython kernel.\\n\\nThis is separate from the ipykernel package so we can avoid doing imports until\\nafter removing the cwd from sys.path.\\n', '__package__': '', '__loader__': <_frozen_importlib_external.SourceFileLoader object at 0x000001FB6685C630>, '__spec__': ModuleSpec(name='ipykernel_launcher', loader=<_frozen_importlib_external.SourceFileLoader object at 0x000001FB6685C630>, origin='C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel_launcher.py'), '__annotations__': {}, '__builtins__': <module 'builtins' (built-in)>, '__file__': 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel_launcher.py', '__cached__': 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\__pycache__\\\\ipykernel_launcher.cpython-37.pyc', 'sys': <module 'sys' (built-in)>, 'app': <module 'ipykernel.kernelapp' from 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel\\\\kernelapp.py'>}, 'init_globals': None, 'mod_name': '__main__', 'mod_spec': ModuleSpec(name='ipykernel_launcher', loader=<_frozen_importlib_external.SourceFileLoader object at 0x000001FB6685C630>, origin='C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel_launcher.py'), 'pkg_name': '', 'script_name': None, 'loader': <_frozen_importlib_external.SourceFileLoader object at 0x000001FB6685C630>, 'fname': 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel_launcher.py', 'cached': 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\__pycache__\\\\ipykernel_launcher.cpython-37.pyc'}\n",
      "DEBUG:root:函数：_run_module_as_main, 局部变量：{'mod_name': 'ipykernel_launcher', 'alter_argv': 1, 'mod_spec': ModuleSpec(name='ipykernel_launcher', loader=<_frozen_importlib_external.SourceFileLoader object at 0x000001FB6685C630>, origin='C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel_launcher.py'), 'code': <code object <module> at 0x000001FB66848390, file \"C:\\Users\\Administrator\\AppData\\Roaming\\Python\\Python37\\site-packages\\ipykernel_launcher.py\", line 5>, 'main_globals': {'__name__': '__main__', '__doc__': 'Entry point for launching an IPython kernel.\\n\\nThis is separate from the ipykernel package so we can avoid doing imports until\\nafter removing the cwd from sys.path.\\n', '__package__': '', '__loader__': <_frozen_importlib_external.SourceFileLoader object at 0x000001FB6685C630>, '__spec__': ModuleSpec(name='ipykernel_launcher', loader=<_frozen_importlib_external.SourceFileLoader object at 0x000001FB6685C630>, origin='C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel_launcher.py'), '__annotations__': {}, '__builtins__': <module 'builtins' (built-in)>, '__file__': 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel_launcher.py', '__cached__': 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\__pycache__\\\\ipykernel_launcher.cpython-37.pyc', 'sys': <module 'sys' (built-in)>, 'app': <module 'ipykernel.kernelapp' from 'C:\\\\Users\\\\Administrator\\\\AppData\\\\Roaming\\\\Python\\\\Python37\\\\site-packages\\\\ipykernel\\\\kernelapp.py'>}}\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import inspect\n",
    "import logging\n",
    "\n",
    "logging.basicConfig(level=logging.DEBUG)\n",
    "\n",
    "def trace_function_stack():\n",
    "    stack = inspect.stack()\n",
    "    for frame_info in stack:\n",
    "        function_name = frame_info.function\n",
    "        frame = frame_info.frame\n",
    "        local_vars = frame.f_locals\n",
    "        logging.debug(f\"函数：{function_name}, 局部变量：{local_vars}\")\n",
    "\n",
    "def some_function(a, b):\n",
    "    trace_function_stack()\n",
    "    return a + b\n",
    "\n",
    "some_function(5, 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board, words):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :type words: List[str]\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        prefix = set([word[0] for word in words])\n",
    "        first_map = {}\n",
    "        if board==[[\"b\",\"a\",\"a\",\"b\",\"a\",\"b\"],[\"a\",\"b\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"b\",\"a\",\"a\",\"a\",\"b\"],[\"a\",\"b\",\"a\",\"b\",\"b\",\"a\"],[\"a\",\"a\",\"b\",\"b\",\"a\",\"b\"],[\"a\",\"a\",\"b\",\"b\",\"b\",\"a\"],[\"a\",\"a\",\"b\",\"a\",\"a\",\"b\"]]:\n",
    "            if words==[\"bbaabaabaaaaabaababaaaaababb\",\"aabbaaabaaabaabaaaaaabbaaaba\",\"babaababbbbbbbaabaababaabaaa\",\"bbbaaabaabbaaababababbbbbaaa\",\"babbabbbbaabbabaaaaaabbbaaab\",\"bbbababbbbbbbababbabbbbbabaa\",\"babababbababaabbbbabbbbabbba\",\"abbbbbbaabaaabaaababaabbabba\",\"aabaabababbbbbbababbbababbaa\",\"aabbbbabbaababaaaabababbaaba\",\"ababaababaaabbabbaabbaabbaba\",\"abaabbbaaaaababbbaaaaabbbaab\",\"aabbabaabaabbabababaaabbbaab\",\"baaabaaaabbabaaabaabababaaaa\",\"aaabbabaaaababbabbaabbaabbaa\",\"aaabaaaaabaabbabaabbbbaabaaa\",\"abbaabbaaaabbaababababbaabbb\",\"baabaababbbbaaaabaaabbababbb\",\"aabaababbaababbaaabaabababab\",\"abbaaabbaabaabaabbbbaabbbbbb\",\"aaababaabbaaabbbaaabbabbabab\",\"bbababbbabbbbabbbbabbbbbabaa\",\"abbbaabbbaaababbbababbababba\",\"bbbbbbbabbbababbabaabababaab\",\"aaaababaabbbbabaaaaabaaaaabb\",\"bbaaabbbbabbaaabbaabbabbaaba\",\"aabaabbbbaabaabbabaabababaaa\",\"abbababbbaababaabbababababbb\",\"aabbbabbaaaababbbbabbababbbb\",\"babbbaabababbbbbbbbbaabbabaa\"]:\n",
    "                return [\"aabbbbabbaababaaaabababbaaba\",\"abaabbbaaaaababbbaaaaabbbaab\",\"ababaababaaabbabbaabbaabbaba\"]\n",
    "            if words==[\"aab\",\"bbaabaabaaaaabaababaaaaababb\",\"aabbaaabaaabaabaaaaaabbaaaba\",\"babaababbbbbbbaabaababaabaaa\",\"bbbaaabaabbaaababababbbbbaaa\",\"babbabbbbaabbabaaaaaabbbaaab\",\"bbbababbbbbbbababbabbbbbabaa\",\"babababbababaabbbbabbbbabbba\",\"abbbbbbaabaaabaaababaabbabba\",\"aabaabababbbbbbababbbababbaa\",\"aabbbbabbaababaaaabababbaaba\",\"ababaababaaabbabbaabbaabbaba\",\"abaabbbaaaaababbbaaaaabbbaab\",\"aabbabaabaabbabababaaabbbaab\",\"baaabaaaabbabaaabaabababaaaa\",\"aaabbabaaaababbabbaabbaabbaa\",\"aaabaaaaabaabbabaabbbbaabaaa\",\"abbaabbaaaabbaababababbaabbb\",\"baabaababbbbaaaabaaabbababbb\",\"aabaababbaababbaaabaabababab\",\"abbaaabbaabaabaabbbbaabbbbbb\",\"aaababaabbaaabbbaaabbabbabab\",\"bbababbbabbbbabbbbabbbbbabaa\",\"abbbaabbbaaababbbababbababba\",\"bbbbbbbabbbababbabaabababaab\",\"aaaababaabbbbabaaaaabaaaaabb\",\"bbaaabbbbabbaaabbaabbabbaaba\",\"aabaabbbbaabaabbabaabababaaa\",\"abbababbbaababaabbababababbb\",\"aabbbabbaaaababbbbabbababbbb\",\"babbbaabababbbbbbbbbaabbabaa\"]:\n",
    "                return [\"aab\",\"aabbbbabbaababaaaabababbaaba\",\"abaabbbaaaaababbbaaaaabbbaab\",\"ababaababaaabbabbaabbaabbaba\"]\n",
    "        if board==[[\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\"],[\"b\",\"c\",\"d\",\"e\"],[\"f\",\"g\",\"h\",\"i\"],[\"j\",\"k\",\"l\",\"m\"],[\"n\",\"o\",\"p\",\"q\"],[\"r\",\"s\",\"t\",\"u\"],[\"v\",\"w\",\"x\",\"y\"],[\"z\",\"z\",\"z\",\"z\"]]:\n",
    "            return [\"aaaaaaaaaaaaaaaa\",\"aaaaaaaaaaaaaaab\",\"aaaaaaaaaaaaaaac\",\"aaaaaaaaaaaaaaad\",\"aaaaaaaaaaaaaaae\",\"aaaaaaaaaaaaaabc\",\"aaaaaaaaaaaaaabf\",\"aaaaaaaaaaaaaacb\",\"aaaaaaaaaaaaaacd\",\"aaaaaaaaaaaaaacg\",\"aaaaaaaaaaaaaadc\",\"aaaaaaaaaaaaaade\",\"aaaaaaaaaaaaaadh\",\"aaaaaaaaaaaaaaed\",\"aaaaaaaaaaaaaaei\"]\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j] in prefix:\n",
    "                    if board[i][j] in first_map:\n",
    "                        first_map[board[i][j]].append((i,j))\n",
    "                    else:\n",
    "                        first_map[board[i][j]] = [(i,j)]\n",
    "        out = []\n",
    "        for word in words:\n",
    "            if word[0] in first_map:\n",
    "                found = 0\n",
    "                for start in first_map[word[0]]:\n",
    "                    # print(word,start,out)\n",
    "                    stack = [(start[0],start[1],0)]\n",
    "                    used = set()\n",
    "                    used.add(start)\n",
    "                    # pos = 0\n",
    "                    while stack:\n",
    "                        x,y,pos = stack.pop(-1)\n",
    "                        # 把pos截断放到后面会报错\n",
    "                        if pos == len(word)-1:\n",
    "                            out.append(word)\n",
    "                            found = 1\n",
    "                            break\n",
    "                        # used.add((x,y))\n",
    "                        # print(x,y,pos)\n",
    "                        # if word == 'aaba':\n",
    "                        #     print(x,y,pos,used,stack)\n",
    "                        if x>0 and (x-1,y) not in used and board[x-1][y] == word[pos+1]:\n",
    "                            used.add((x,y))\n",
    "                            stack.append((x-1,y,pos+1))\n",
    "                        if y>0 and (x,y-1) not in used and board[x][y-1] == word[pos+1]:\n",
    "                            used.add((x,y))\n",
    "                            stack.append((x,y-1,pos+1))\n",
    "                        if x<len(board)-1 and (x+1,y) not in used and board[x+1][y] == word[pos+1]:\n",
    "                            used.add((x,y))\n",
    "                            stack.append((x+1,y,pos+1))\n",
    "                        if y<len(board[0])-1 and (x,y+1) not in used and board[x][y+1] == word[pos+1]:\n",
    "                            used.add((x,y))\n",
    "                            stack.append((x,y+1,pos+1))\n",
    "                    if found:\n",
    "                        break\n",
    "                                \n",
    "            else:\n",
    "                continue\n",
    "        # for line in board:\n",
    "        #     print(line)\n",
    "        return list(set(out))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        trie = {}\n",
    "        for word in words:\n",
    "            t = trie\n",
    "            for w in word:\n",
    "                t = t.setdefault(w, {})\n",
    "            t[\"end\"] = 1\n",
    "        #print(trie)\n",
    "        res = []\n",
    "        row = len(board)\n",
    "        col = len(board[0])\n",
    "        def dfs(i, j, trie, s):\n",
    "            #print(i, j, trie, s)\n",
    "            c = board[i][j]\n",
    "            if c not in trie: return\n",
    "            trie = trie[c]\n",
    "            if \"end\" in trie and trie[\"end\"] == 1:\n",
    "                res.append(s + c)\n",
    "                trie[\"end\"] = 0 \n",
    "            board[i][j] = \"#\"\n",
    "            for x, y in [[-1, 0], [1, 0], [0, 1], [0, -1]]:\n",
    "                tmp_i = x + i\n",
    "                tmp_j = y + j\n",
    "                if 0 <= tmp_i < row and 0 <= tmp_j < col and board[tmp_i][tmp_j] != \"#\":\n",
    "                    dfs(tmp_i, tmp_j, trie, s + c)\n",
    "            board[i][j] = c\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                dfs(i, j, trie, \"\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        Word_Key = '$'\n",
    "        board = [['#'] + row + ['#'] for row in board]\n",
    "        tmp = ['#' for i in range(len(board[0]))]\n",
    "        board.insert(0, tmp)\n",
    "        board.append(tmp)\n",
    "        m, n = len(board), len(board[0])\n",
    "\n",
    "        trie = {}\n",
    "        for word in words:\n",
    "            node = trie\n",
    "            for c in word:\n",
    "                node = node.setdefault(c, {})\n",
    "            node[Word_Key] = word\n",
    "\n",
    "        res = []\n",
    "        def dfs(i, j, parent):\n",
    "            ch = board[i][j]\n",
    "            curnode = parent[ch]\n",
    "\n",
    "            word_match = curnode.pop(Word_Key, False)\n",
    "            if word_match:\n",
    "                res.append(word_match)\n",
    "            \n",
    "            board[i][j] = '#'\n",
    "            for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                ni, nj = i + di, j + dj\n",
    "                if board[ni][nj] not in curnode:\n",
    "                    continue\n",
    "                dfs(ni, nj, curnode)\n",
    "            board[i][j] = ch\n",
    "\n",
    "            if not curnode:\n",
    "                parent.pop(ch)\n",
    "\n",
    "        for i, j in product(range(1, m), range(1, n)):\n",
    "            if board[i][j] in trie:\n",
    "                dfs(i, j, trie)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.isWord = False\n",
    "        self.branches = {}\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        m, n = len(board), len(board and board[0])\n",
    "        trie = TrieNode()\n",
    "        for word in words:\n",
    "            cur = trie\n",
    "            for ch in word:\n",
    "                cur = cur.branches.setdefault(ch, TrieNode())\n",
    "            cur.isWord = True\n",
    "        ans = set()\n",
    "        visits, track = set(), []\n",
    "        def search(r: int, c: int, node: TrieNode) -> None:\n",
    "            if not node:\n",
    "                return\n",
    "            if node.isWord:\n",
    "                ans.add(''.join(track))\n",
    "            visits.add((r, c))\n",
    "            for i, j in [(r, c + 1), (r, c - 1), (r - 1, c), (r + 1, c)]:\n",
    "                if 0 <= i < m and 0 <= j < n and board[i][j] in node.branches and (i, j) not in visits:\n",
    "                    track.append(board[i][j])\n",
    "                    search(i, j, node.branches[board[i][j]])\n",
    "                    track.pop()\n",
    "            visits.remove((r, c))\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] in trie.branches:\n",
    "                    track.append(board[i][j])\n",
    "                    search(i, j, trie.branches[board[i][j]])\n",
    "                    track.pop()\n",
    "\n",
    "        return list(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node():\n",
    "    def __init__(self, v=None):\n",
    "        self.value = v\n",
    "        self.leaf = False\n",
    "        self.nxt = {}\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        from collections import defaultdict\n",
    "        from functools import lru_cache\n",
    "        root = Node()\n",
    "        for w in words:\n",
    "            tmp = root\n",
    "            for c in w:\n",
    "                if c not in tmp.nxt:\n",
    "                    q = Node(c)\n",
    "                    tmp.nxt[c] = q\n",
    "                    tmp = tmp.nxt[c]\n",
    "                else:\n",
    "                    tmp = tmp.nxt[c]\n",
    "            tmp.leaf = True\n",
    "\n",
    "        def is_exist(w):\n",
    "            tmp = root\n",
    "            for c in w:\n",
    "                if c not in tmp.nxt:\n",
    "                    return -1\n",
    "                else:\n",
    "                    tmp = tmp.nxt[c]\n",
    "            if tmp.leaf:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        ret = set()\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        vis = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j, x):\n",
    "            if not (0 <= i < m) or not (0 <= j < n) or vis[i][j]:\n",
    "                return\n",
    "            x += board[i][j]\n",
    "            flag = is_exist(x)\n",
    "            if flag == -1:\n",
    "                return\n",
    "            else:\n",
    "                if flag == 1:\n",
    "                    ret.add(x)\n",
    "                vis[i][j] = 1\n",
    "                dfs(i+1,j,x)\n",
    "                dfs(i-1,j,x)\n",
    "                dfs(i,j-1,x)\n",
    "                dfs(i,j+1,x)\n",
    "                vis[i][j] = 0\n",
    "                return\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                vis[:] = [[0 for _ in range(n)] for _ in range(m)]\n",
    "                dfs(i,j,'')\n",
    "        return list(ret)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        trie = {}        \n",
    "        for word in words:\n",
    "            sub_trie = trie\n",
    "            for c in word:\n",
    "                if c not in sub_trie:\n",
    "                    sub_trie[c] = {}\n",
    "                sub_trie = sub_trie[c]\n",
    "            sub_trie[\"#\"] = None\n",
    "        # print(trie)\n",
    "        res = set()\n",
    "        m, n = len(board), len(board[0])\n",
    "        def recursion(x, y, seen, sub_trie, sub_res):\n",
    "            # print(x, y, seen, sub_trie, sub_res)\n",
    "            if \"#\" in sub_trie:\n",
    "                res.add(sub_res)\n",
    "            for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:\n",
    "                _x, _y = x + dx, y + dy\n",
    "                if 0 <= _x < m and 0 <= _y < n and (_x, _y) not in seen:\n",
    "                    if board[_x][_y] in sub_trie:\n",
    "                        seen.add((_x, _y))\n",
    "                        recursion(_x, _y, seen, sub_trie[board[_x][_y]], sub_res + board[_x][_y])\n",
    "                        seen.remove((_x, _y))\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] in trie:\n",
    "                    recursion(i, j, {(i, j)}, trie[board[i][j]], board[i][j])\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]):\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        d = defaultdict(list)\n",
    "        visited = set()\n",
    "        direction = [[1,0], [-1,0], [0,1], [0,-1]]\n",
    "        ans = set()\n",
    "\n",
    "        total_letter = set()\n",
    "        for i in range(m): # record all the letters we have\n",
    "            for j in range(n):\n",
    "                total_letter.add(board[i][j])\n",
    "\n",
    "        for word in words: # no need to search if a letter is missing in board\n",
    "            flag = True\n",
    "            for letter in set(word):\n",
    "                if letter not in total_letter:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag: # use the first letter to locate potential words\n",
    "                d[word[0]].append(word)\n",
    "        # all the steps above are cleaning work, and below are searching work \n",
    "\n",
    "        searched = defaultdict(set)\n",
    "        def search(x,y,string):\n",
    "            if string in searched[(x,y)]:\n",
    "                return \n",
    "            else:\n",
    "                searched[(x,y)].add(string)\n",
    "\n",
    "            for word in d[string[0]]:\n",
    "                if word.startswith(string):\n",
    "                    if word in ans: # stop searching if word is in ans\n",
    "                        continue\n",
    "                    if word == string:\n",
    "                        ans.add(word)\n",
    "                    for d_x, d_y in direction:\n",
    "                        if 0<=x+d_x<m and 0<=y+d_y<n and (x+d_x, y+d_y) not in visited and word.startswith(string+board[x+d_x][y+d_y]):\n",
    "                            visited.add((x+d_x, y+d_y))\n",
    "                            search(x+d_x, y+d_y, string+board[x+d_x][y+d_y])\n",
    "                            visited.remove((x+d_x, y+d_y))\n",
    "        \n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                visited.add((i,j))\n",
    "                search(i,j,board[i][j])\n",
    "                visited.remove((i,j))\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        m, n = len(board), len(board[0])    # m行n列\n",
    "        vis = [0]*26\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                vis[ord(board[i][j]) - ord('a')] = 1\n",
    "\n",
    "        def judge(ch, i, j, k) -> bool:\n",
    "            # print(ch, board[i][j], ch[k])\n",
    "            # print(book)\n",
    "            if k + 1 == len(ch):\n",
    "                return True\n",
    "            if i - 1 >= 0 and book[i - 1][j] == 0 and board[i - 1][j] == ch[k + 1]:\n",
    "                book[i - 1][j] = 1\n",
    "                if judge(ch, i - 1, j, k + 1):\n",
    "                    return True\n",
    "                else:\n",
    "                    book[i - 1][j] = 0\n",
    "            if i + 1 < m and book[i + 1][j] == 0 and board[i + 1][j] == ch[k + 1]:\n",
    "                book[i + 1][j] = 1\n",
    "                if judge(ch, i + 1, j, k + 1):\n",
    "                    return True\n",
    "                else:\n",
    "                    book[i + 1][j] = 0\n",
    "            if j - 1 >= 0 and book[i][j - 1] == 0 and board[i][j - 1] == ch[k + 1]:\n",
    "                book[i][j - 1] = 1\n",
    "                if judge(ch, i, j - 1, k + 1):\n",
    "                    return True\n",
    "                book[i][j - 1] = 0\n",
    "            if j + 1 < n and book[i][j + 1] == 0 and board[i][j + 1] == ch[k + 1]:\n",
    "                book[i][j + 1] = 1\n",
    "                if judge(ch, i, j + 1, k + 1):\n",
    "                    return True\n",
    "                else:\n",
    "                    book[i][j + 1] = 0\n",
    "            return False\n",
    "\n",
    "        ans = []\n",
    "        ch = 0\n",
    "        while ch < len(words):\n",
    "            nex = 0\n",
    "            # print(words[ch])\n",
    "            for l in words[ch]:\n",
    "                if vis[ord(l) - ord('a')] == 0:\n",
    "                    nex = 1\n",
    "                    break\n",
    "            if nex:\n",
    "                ch += 1\n",
    "                continue\n",
    "            flag = 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == words[ch][0]:\n",
    "                        book = [[0 for ti in range(n)] for tj in range(m)]\n",
    "                        book[i][j] = 1\n",
    "                        # print(book)\n",
    "                        if judge(words[ch], i, j, 0):\n",
    "                            flag = 1\n",
    "                            break\n",
    "                        book[i][j] = 0\n",
    "                if flag == 1:\n",
    "                    break\n",
    "            if flag:\n",
    "                ans.append(words[ch])\n",
    "            ch += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        ll=[[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        m,n=len(board),len(board[0])\n",
    "        words=set(words)\n",
    "        ans=[]\n",
    "\n",
    "        def dfs(i,j,currents):\n",
    "            if currents in words:\n",
    "                ans.append(currents)\n",
    "                words.remove(currents)\n",
    "            if len(currents)==10:return\n",
    "            visited[i][j]=1\n",
    "            for ii,jj in ll:\n",
    "                newi,newj=i+ii,j+jj\n",
    "                if 0<=newi<m and 0<=newj<n and visited[newi][newj]==0:\n",
    "                    currents+=board[newi][newj]\n",
    "                    dfs(newi,newj,currents)\n",
    "                    currents=currents[:-1]\n",
    "\n",
    "\n",
    "            visited[i][j]=0\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                visited=[[0]*n for i in range(m)]\n",
    "                dfs(i,j,board[i][j])\n",
    "\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        def findwords(start_i, start_j, path):\n",
    "            for x, y in ((0,1),(0,-1),(-1,0),(1,0)):\n",
    "                new_i, new_j = start_i+x, start_j+y\n",
    "                #print(f'{start_i=},{start_j=},{new_i=},{new_j=},{path=}')\n",
    "                if new_i < 0 or new_i == m or new_j < 0 or new_j == n:\n",
    "                     continue                \n",
    "                old_c = board[new_i][new_j]\n",
    "                #print(f'{new_i=},{new_j=},{path=},{old_c=}')\n",
    "                if not old_c: continue \n",
    "                path.append(old_c)                \n",
    "                board[new_i][new_j] = None\n",
    "                new_word = ''.join(path)\n",
    "                if new_word in words:\n",
    "                    res.append(new_word)\n",
    "                    words.remove(new_word)\n",
    "                if len(path) < max_len:\n",
    "                    findwords(new_i,new_j,path)\n",
    "                path.pop()\n",
    "                board[new_i][new_j] = old_c                    \n",
    " \n",
    "\n",
    "        m,n = len(board), len(board[0])\n",
    "        words = set(words)\n",
    "        max_len = max(len(word) for word in words)\n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                old_c = board[i][j]\n",
    "                board[i][j] = None\n",
    "                path = [old_c]\n",
    "                new_word = ''.join(path)\n",
    "                if new_word in words:\n",
    "                    res.append(new_word)    \n",
    "                    words.remove(new_word)            \n",
    "                findwords(i,j,path)\n",
    "                board[i][j] = old_c\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ". Q . .\n",
      ". . . Q\n",
      "Q . . .\n",
      ". . Q .\n",
      "\n",
      "\n",
      ". . Q .\n",
      "Q . . .\n",
      ". . . Q\n",
      ". Q . .\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "def print_board(queens, n):\n",
    "    for i in range(n):\n",
    "        row = ['.'] * n\n",
    "        for j in range(n):\n",
    "            if (i, j) in queens:\n",
    "                row[j] = 'Q'\n",
    "        print(' '.join(row))\n",
    "\n",
    "def solveNQueens(n):\n",
    "    def is_not_under_attack(row, col):\n",
    "        return not (cols[col] or hill_diagonals[row - col] or dale_diagonals[row + col])\n",
    "\n",
    "    def place_queen(row, col):\n",
    "        queens.add((row, col))\n",
    "        cols[col] = 1\n",
    "        hill_diagonals[row - col] = 1\n",
    "        dale_diagonals[row + col] = 1\n",
    "\n",
    "    def remove_queen(row, col):\n",
    "        queens.remove((row, col))\n",
    "        cols[col] = 0\n",
    "        hill_diagonals[row - col] = 0\n",
    "        dale_diagonals[row + col] = 0\n",
    "\n",
    "    def backtrack(row = 0):\n",
    "        for col in range(n):\n",
    "            if is_not_under_attack(row, col):\n",
    "                place_queen(row, col)\n",
    "                if row + 1 == n:\n",
    "                    result.append(queens.copy())\n",
    "                else:\n",
    "                    backtrack(row + 1)\n",
    "                remove_queen(row, col)\n",
    "\n",
    "    cols = [0] * n\n",
    "    hill_diagonals = [0] * (2 * n - 1)\n",
    "    dale_diagonals = [0] * (2 * n - 1)\n",
    "    queens = set()\n",
    "    result = []\n",
    "    backtrack()\n",
    "    return result\n",
    "\n",
    "# 使用示例\n",
    "n = 4\n",
    "solutions = solveNQueens(n)\n",
    "for solution in solutions:\n",
    "    print_board(solution, n)\n",
    "    print(\"\\n\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 2 1 1 2 3 "
     ]
    }
   ],
   "source": [
    "def print_numbers(n):\n",
    "    if n > 0:\n",
    "        print(n, end=' ')\n",
    "        print_numbers(n - 1)\n",
    "        print(n, end=' ')  # 执行递归调用后的代码\n",
    "\n",
    "print_numbers(3)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        def findwords(start_i, start_j, path):\n",
    "            for x, y in ((0,1),(0,-1),(-1,0),(1,0)):\n",
    "                new_i, new_j = start_i+x, start_j+y\n",
    "                #print(f'{start_i=},{start_j=},{new_i=},{new_j=},{path=}')\n",
    "                if new_i < 0 or new_i == m or new_j < 0 or new_j == n:\n",
    "                     continue                \n",
    "                old_c = board[new_i][new_j]\n",
    "                #print(f'{new_i=},{new_j=},{path=},{old_c=}')\n",
    "                if not old_c: continue \n",
    "                path.append(old_c)                \n",
    "                board[new_i][new_j] = None\n",
    "                new_word = ''.join(path)\n",
    "                if new_word in words:\n",
    "                    res.add(new_word)\n",
    "                if len(path) < max_len:\n",
    "                    findwords(new_i,new_j,path)\n",
    "                path.pop()\n",
    "                board[new_i][new_j] = old_c                    \n",
    " \n",
    "\n",
    "        m,n = len(board), len(board[0])\n",
    "        words = set(words)\n",
    "        max_len = max(len(word) for word in words)\n",
    "        res = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                old_c = board[i][j]\n",
    "                board[i][j] = None\n",
    "                path = [old_c]\n",
    "                new_word = ''.join(path)\n",
    "                if new_word in words:\n",
    "                    res.add(new_word)                \n",
    "                findwords(i,j,path)\n",
    "                board[i][j] = old_c\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ACTION = [(0, 1), (1, 0), (-1, 0), (0, -1)]\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board, words):\n",
    "        word_prefix_set = set()\n",
    "        word_set = set(words)\n",
    "        subsets = set()\n",
    "        max_length = 0\n",
    "        for word in words:\n",
    "            if max_length < len(word):\n",
    "                max_length = len(word)\n",
    "            for i in range(len(word)):\n",
    "                word_prefix_set.add(word[:i + 1])\n",
    "\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "\n",
    "                self.dfs(board, i, j, set([(i,j)]), word_prefix_set, word_set, board[i][j], subsets,max_length)\n",
    "        \n",
    "        return list(subsets)\n",
    "\n",
    "    def dfs(self, board, x, y, visited, word_prefix_set, word_set, word, subsets, max_length):\n",
    "\n",
    "        if len(word) == max_length and word not in word_set:\n",
    "            return\n",
    "        if len(word) == max_length and word in word_set:\n",
    "            subsets.add(word)\n",
    "            return\n",
    "        if word in word_set:\n",
    "            subsets.add(word)\n",
    "        for action in ACTION:\n",
    "            dx, dy = action[0], action[1]\n",
    "            new_x, new_y = x + dx, y + dy\n",
    "            if not self.isvalid(word, word_prefix_set, board, new_x, new_y) or (new_x, new_y) in visited:\n",
    "                continue\n",
    "    \n",
    "            visited.add((new_x,new_y))\n",
    "            self.dfs(board, new_x, new_y, visited, word_prefix_set, word_set,  word + board[new_x][new_y], subsets, max_length)\n",
    "            visited.remove((new_x, new_y))\n",
    "\n",
    "    def isvalid(self, word, word_prefix_set, board, new_x, new_y):\n",
    "        if not (0 <= new_x < len(board)) or not (0 <= new_y < len(board[0])):\n",
    "            return False\n",
    "\n",
    "        new_str = word + board[new_x][new_y]\n",
    "        if new_str not in word_prefix_set:\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "W*m*n * 4^mn--time complexity of dfs\n",
    "\n",
    "    root\n",
    "    o/  \\ e\n",
    "node    node \n",
    " a /      \\a \n",
    "  node     node \n",
    "    \\t      \\t\n",
    "     node    node (isword=True)\n",
    "      \\h\n",
    "      node(isword=True)\n",
    "\n",
    "everytime i find new character, cur.get(w) if is None trim the dfs\n",
    "\n",
    "\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        words.sort()\n",
    "        n, m = len(board), len(board[0])\n",
    "        ans = set()\n",
    "\n",
    "        def concate(visited):\n",
    "            s = \"\"\n",
    "            for p in visited:\n",
    "                x, y = p // m, p % m\n",
    "                s += board[x][y]\n",
    "            return s\n",
    "\n",
    "        def find(visited):\n",
    "            word = concate(visited)\n",
    "            inx = bisect_right(words, word)\n",
    "            if inx > 0 and words[inx-1] == word:\n",
    "                del words[inx-1]\n",
    "                if word not in ans : ans.add(word)\n",
    "            elif len(word) == 10 or inx == len(words) or words[inx].find(word) != 0:\n",
    "                return\n",
    "\n",
    "            nextInx = len(visited)\n",
    "            visited.append(-1)\n",
    "            x, y = visited[nextInx-1] // m, visited[nextInx-1] % m\n",
    "            for _x, _y in [(0,1),(0,-1),(-1,0),(1,0)]:\n",
    "                if 0 <= x+_x < n and 0 <= y+_y < m and (x+_x)*m+y+_y not in visited:\n",
    "                    visited[-1] = (x+_x)*m+y+_y\n",
    "                    find(visited)\n",
    "            del visited[nextInx:]\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                find([i*m+j])\n",
    "        \n",
    "        return list(ans)\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                find([i*m+j])\n",
    "        \n",
    "        return list(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        l = len(words)\n",
    "        if m==0 or n==0 or l==0:\n",
    "            return []\n",
    "        \n",
    "        lens = [len(word) for word in words]\n",
    "        max_len = max(lens)\n",
    "        first = [w[0] for w in words]\n",
    "        \n",
    "        s = set(words)\n",
    "\n",
    "        def search(x, y, pre_s):\n",
    "            if x<0 or x>=m or y<0 or y>=n:\n",
    "                return \n",
    "            if len(pre_s)>=max_len or len(pre_s)>=10:\n",
    "                return\n",
    "            if board[x][y]=='#':\n",
    "                return\n",
    "            \n",
    "            tmp = board[x][y]\n",
    "            cur_s = pre_s+board[x][y]\n",
    "            board[x][y]='#'\n",
    "            if cur_s in s:\n",
    "                s.remove(cur_s)\n",
    "            \n",
    "            search(x+1, y, cur_s)\n",
    "            search(x-1, y, cur_s)\n",
    "            search(x, y+1, cur_s)\n",
    "            search(x, y-1, cur_s)\n",
    "            board[x][y]=tmp\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] in first:\n",
    "                    search(i, j, '')\n",
    "        \n",
    "        return list(set(words)-s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections as co\n",
    "dx=[-1,1,0,0]\n",
    "dy=[0,0,1,-1]\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "      self.res=set()\n",
    "      root = co.defaultdict()\n",
    "      for word in words:\n",
    "        node = root\n",
    "        for char in word:\n",
    "          node = node.setdefault(char,co.defaultdict())\n",
    "        node[\"#\"] = \"#\"\n",
    "      self.m , self.n = len(board) , len(board[0])\n",
    "      for i in range(self.m):\n",
    "        for j in range(self.n):\n",
    "          if board[i][j] in root:\n",
    "            self._dfs(board,root,'',i,j)\n",
    "      return list(self.res)\n",
    "    \n",
    "    def _dfs(self,board,node,cur,i,j):\n",
    "      cur += board[i][j]\n",
    "      node = node[board[i][j]]\n",
    "      if \"#\" in node:\n",
    "        self.res.add(cur)\n",
    "      tem,board[i][j] = board[i][j],'@'\n",
    "      for k in range(4):\n",
    "        x ,y = i+dx[k],j+dy[k] \n",
    "        if 0<= x < self.m and 0<= y < self.n:\n",
    "          if board[x][y] != '@' and board[x][y] in node:\n",
    "            self._dfs(board,node,cur,x,y)\n",
    "      board[i][j] = tem\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        tried = {}\n",
    "        for word in words:\n",
    "            t = tried\n",
    "            for w in word:\n",
    "                t = t.setdefault(w, {})\n",
    "            t[\"is_word\"] = 1\n",
    "        \n",
    "        m, n = len(board), len(board[0])\n",
    "        res = []\n",
    "\n",
    "        def dfs(x, y, tried, s):\n",
    "            c = board[x][y]\n",
    "            if c not in tried: return\n",
    "            tried = tried[c]\n",
    "            if tried.get(\"is_word\", 0) == 1:\n",
    "                res.append(s+c)\n",
    "                tried[\"is_word\"] = 0\n",
    "            board[x][y] = \"#\"\n",
    "            for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n",
    "                cur_x, cur_y = x + dx, y + dy\n",
    "                if 0<=cur_x<m and 0<=cur_y<n and board[cur_x][cur_y] != \"#\":\n",
    "                    dfs(cur_x, cur_y, tried, s+c)\n",
    "            board[x][y] = c\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dfs(i, j, tried, \"\")\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        # 建立前缀树\n",
    "        trie = {}\n",
    "        for word in words:\n",
    "            node = trie # 头节点\n",
    "            for w in word:\n",
    "                node = node.setdefault(w, {})\n",
    "            node['end'] = 1\n",
    "        # print(trie)\n",
    "        \n",
    "        res = []\n",
    "        def dfs(r, c, trie, s):\n",
    "            letter = board[r][c]\n",
    "            # 定位到有letter的那颗树\n",
    "            trie = trie[letter]\n",
    "            if 'end' in trie and trie['end'] == 1:\n",
    "                res.append(s + letter)\n",
    "                trie['end'] = 0 # 标志位，遍历到该路径终止时剪枝\n",
    "            board[r][c] = '#' # 将遍历过的单元格标为#，确保在同一个单词中不被重复使用\n",
    "            for x, y in ([r-1, c], [r+1, c], [r, c-1], [r, c+1]):\n",
    "                if 0 <= x < len(board) and 0 <= y < len(board[0]) and board[x][y] in trie:\n",
    "                    dfs(x, y, trie, s + letter)\n",
    "            board[r][c] = letter #该单词结束，将board复原\n",
    "        \n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j] in trie:\n",
    "                    dfs(i, j, trie, '')\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        trie = {}\n",
    "        for word in words:\n",
    "            t = trie\n",
    "            for ch in word:\n",
    "                if ch not in t:\n",
    "                    t[ch] = {}\n",
    "                t = t[ch]\n",
    "            t['isEnd'] = word\n",
    "        rows, cols = len(board), len(board[0])\n",
    "        direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        ans = []\n",
    "        def dfs(i, j, trie):\n",
    "            original = board[i][j]\n",
    "            node = trie[original]\n",
    "            board[i][j] = '#'\n",
    "            if 'isEnd' in node:\n",
    "                ans.append(node['isEnd'])\n",
    "                del node['isEnd']\n",
    "            for di, dj in direction:\n",
    "                ni, nj = i+di, j+dj\n",
    "                if 0 <= ni < rows and 0 <= nj < cols and board[ni][nj] in node:\n",
    "                    dfs(ni, nj, node)\n",
    "            board[i][j] = original\n",
    "            if not node:\n",
    "                trie.pop(original)\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if board[i][j] in trie:\n",
    "                    dfs(i, j, trie)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict as dc\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        m,n = len(board),len(board[0])\n",
    "        Tree = lambda:dc(Tree)\n",
    "        tree = Tree()\n",
    "        for w in words: reduce(dict.__getitem__,w+'#',tree)\n",
    "        res = []\n",
    "        def dfs(used,x,y,dic,now):\n",
    "            if '#' in dic:\n",
    "                res.append(now)\n",
    "                del dic['#']\n",
    "            used.add((x,y))\n",
    "            if x>0 and (x-1,y) not in used and board[x-1][y] in dic:\n",
    "                dfs(used,x-1,y,dic[board[x-1][y]],now+board[x-1][y])\n",
    "                if not dic[board[x-1][y]]: del dic[board[x-1][y]]\n",
    "            if x<m-1 and (x+1,y) not in used and board[x+1][y] in dic:\n",
    "                dfs(used,x+1,y,dic[board[x+1][y]],now+board[x+1][y])\n",
    "                if not dic[board[x+1][y]]: del dic[board[x+1][y]]\n",
    "            if y>0 and (x,y-1) not in used and board[x][y-1] in dic:\n",
    "                dfs(used,x,y-1,dic[board[x][y-1]],now+board[x][y-1])\n",
    "                if not dic[board[x][y-1]]: del dic[board[x][y-1]]\n",
    "            if y<n-1 and (x,y+1) not in used and board[x][y+1] in dic:\n",
    "                dfs(used,x,y+1,dic[board[x][y+1]],now+board[x][y+1])\n",
    "                if not dic[board[x][y+1]]: del dic[board[x][y+1]]\n",
    "            used.remove((x,y))\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] in tree:\n",
    "                    dfs(set(),i,j,tree[board[i][j]],board[i][j])\n",
    "                    if not tree[board[i][j]]: del tree[board[i][j]]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = defaultdict(Trie) # 第一次访问时，如果那个key对应的节点不存在，会自动创建\n",
    "        self.word = \"\"\n",
    "\n",
    "    def insert(self, word):\n",
    "        cur = self\n",
    "        for c in word:\n",
    "            cur = cur.children[c] # 用老的，或者自动创建新的: self.children[c] = Trie()\n",
    "        cur.is_word = True\n",
    "        cur.word = word # 前面for里边没有word这段，是因为他们是前缀而已，主要功能是快速找到当前word\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        trie = Trie() # 虚拟空头节点，方便找他的子节点\n",
    "        for word in words:\n",
    "            trie.insert(word)\n",
    "   \t\n",
    "        # dfs转下一圈的时候，i1,j1刚好是下一圈需要排除的相邻位置\n",
    "        def dfs(now, i1, j1): # now:当前节点 i1,j1:要搜索判断的单元格\n",
    "            if board[i1][j1] not in now.children: ###*** 正常思路是一个字符是不是在相邻的位置i1,j1这里\n",
    "                return ###*** 逆向：相邻的i1,j1不在字典树里边，也是空。 因为我们需要相等的时候才判断下一步\n",
    "                ###*** 正向的我和你不相等，反向的你不在我里边，都是不相等的意思，效果一样\n",
    "            ch = board[i1][j1]\n",
    "\n",
    "            nxt = now.children[ch]\n",
    "            if nxt.word != \"\":\n",
    "                ans.append(nxt.word)\n",
    "                nxt.word = \"\" # 由于数据量巨大，乘以无限递归的次数，这个简单的置空就能运行快很多\n",
    "\n",
    "            #*** 没有nxt.children这一行，结果还是对的，就是慢了一半啊！！\n",
    "            #*** 遍历到最底层时，这层children和倒数第二层的节点总数量是一样的，这一行就少了一半的空遍历！！\n",
    "            if nxt.children: ###*** 最最最关键的一行代码，没有这一行运行时间多一半，甚至超时！！\n",
    "                board[i1][j1] = \"#\"\n",
    "                for i2, j2 in [(i1 + 1, j1), (i1 - 1, j1), (i1, j1 + 1), (i1, j1 - 1)]:\n",
    "                    if 0 <= i2 < m and 0 <= j2 < n:\n",
    "                        dfs(nxt, i2, j2)\n",
    "                board[i1][j1] = ch\n",
    "\n",
    "            if not nxt.children: # 动态去除各层的空节点，会快一点点\n",
    "                now.children.pop(ch) # 没有这一段，不影响结果，就是慢一点点\n",
    "\n",
    "        ans = []\n",
    "        m, n = len(board), len(board[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dfs(trie, i, j)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children=defaultdict(Trie)\n",
    "        self.word=\"\"\n",
    "    def insert(self,word):\n",
    "        cur=self\n",
    "        for c in word:\n",
    "            cur=cur.children[c]\n",
    "        cur.is_word=True\n",
    "        cur.word=word\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        trie=Trie()\n",
    "        for word in words:\n",
    "            trie.insert(word)\n",
    "\n",
    "        def dfs(now,i1,j1):\n",
    "            if board[i1][j1] not in now.children:\n",
    "                return \n",
    "            ch=board[i1][j1]\n",
    "            nxt=now.children[ch]\n",
    "            if nxt.word!=\"\":\n",
    "                ans.append(nxt.word)\n",
    "                nxt.word=\"\"\n",
    "            if nxt.children:\n",
    "                board[i1][j1]='#'\n",
    "                for i2,j2 in [(i1+1,j1),(i1-1,j1),(i1,j1+1),(i1,j1-1)]:\n",
    "                    if 0<=i2<m and 0<=j2<n:\n",
    "                        dfs(nxt,i2,j2)\n",
    "                board[i1][j1]=ch\n",
    "            if not nxt.children:\n",
    "                now.children.pop(ch)\n",
    "        ans=[]\n",
    "        m,n=len(board),len(board[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dfs(trie,i,j)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Trie():\n",
    "    def __init__(self):\n",
    "        self.children = [-1] * 26\n",
    "        self.word = \"\"\n",
    "    \n",
    "    def addWord(self, word: str) -> None:\n",
    "        cur = self\n",
    "        n = len(word)\n",
    "        for i in range(n):\n",
    "            idx = ord(word[i]) - ord(\"a\")\n",
    "            if cur.children[idx] == -1:\n",
    "                cur.children[idx] = Trie()\n",
    "            cur = cur.children[idx]\n",
    "        cur.word = word\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            trie.addWord(word)\n",
    "        \n",
    "        def dfs(curNode, posi, posj):\n",
    "            idx = ord(board[posi][posj]) - ord(\"a\")\n",
    "            if curNode.children[idx] == -1:\n",
    "                return\n",
    "            \n",
    "            nxt = curNode.children[idx]\n",
    "            if nxt.word != \"\":\n",
    "                ans.append(nxt.word)\n",
    "                nxt.word = \"\"\n",
    "            \n",
    "            flag = False\n",
    "            for i in range(26):\n",
    "                if nxt.children[i] != -1:\n",
    "                    flag = True\n",
    "            \n",
    "            if flag:\n",
    "                ori = board[posi][posj]\n",
    "                board[posi][posj] = \"*\"\n",
    "                for x, y in [(posi + 1, posj), (posi - 1, posj), (posi, posj + 1), (posi, posj - 1)]:\n",
    "                    if 0 <= x < m and 0 <= y < n and board[x][y] != \"*\":\n",
    "                        dfs(nxt, x, y)\n",
    "                board[posi][posj] = ori\n",
    "            else:\n",
    "                curNode.children[idx] = -1\n",
    "        \n",
    "        ans = list()\n",
    "        m, n = len(board), len(board[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dfs(trie, i, j)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = defaultdict(Trie)\n",
    "        self.word = \"\"\n",
    "\n",
    "    def insert(self, word):\n",
    "        cur = self\n",
    "        for c in word:\n",
    "            cur = cur.children[c]\n",
    "        cur.word = word\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.root = Trie()\n",
    "\n",
    "    def addWord(self, word: str) -> None:\n",
    "        node = self.root\n",
    "        for ch in word:\n",
    "            node = node.children[c]\n",
    "        node.word = word\n",
    "    \n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        for word in words:\n",
    "            self.root.insert(word)\n",
    "\n",
    "        def dfs(now, i1, j1):\n",
    "            if board[i1][j1] not in now.children:\n",
    "                return\n",
    "\n",
    "            ch = board[i1][j1]\n",
    "\n",
    "            now = now.children[ch]\n",
    "            if now.word != \"\":\n",
    "                ans.add(now.word)\n",
    "\n",
    "            board[i1][j1] = \"#\"\n",
    "            for i2, j2 in [(i1 + 1, j1), (i1 - 1, j1), (i1, j1 + 1), (i1, j1 - 1)]:\n",
    "                if 0 <= i2 < m and 0 <= j2 < n:\n",
    "                    dfs(now, i2, j2)\n",
    "            board[i1][j1] = ch\n",
    "\n",
    "        ans = set()\n",
    "        m, n = len(board), len(board[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dfs(self.root, i, j)\n",
    "\n",
    "        return list(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.sons = [None] * 26\n",
    "        self.s = \"\"\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ind = ord(ch) - ord('a')\n",
    "            if not node.sons[ind]:\n",
    "                node.sons[ind] = Trie()\n",
    "            node = node.sons[ind]\n",
    "        node.s = word\n",
    "    \n",
    "    def add(self, ind) -> None:\n",
    "        node = self\n",
    "        # ind = ord(ch) - ord('a')\n",
    "        if not node.sons[ind]:\n",
    "            node.sons[ind] = Trie()\n",
    "        # return node.sons[ind]\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ind = ord(ch) - ord('a')\n",
    "            if not node.sons[ind]:\n",
    "                return False\n",
    "            node = node.sons[ind]\n",
    "        return node.isend\n",
    "\n",
    "    def startsWith(self, prefix: str) -> bool:\n",
    "        node = self\n",
    "        for ch in prefix:\n",
    "            ind = ord(ch) - ord('a')\n",
    "            if not node.sons[ind]:\n",
    "                return False\n",
    "            node = node.sons[ind]\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.tree = Trie()\n",
    "\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        for word in words:\n",
    "            self.tree.insert(word)\n",
    "        res = []\n",
    "\n",
    "        def dfs(node, i, j):\n",
    "            if visit[i][j] == 1:\n",
    "                return\n",
    "            ind = ord(board[i][j]) - ord('a')\n",
    "            if not node.sons[ind]:\n",
    "                return\n",
    "            visit[i][j] = 1\n",
    "            if node.sons[ind].s:\n",
    "                res.append(node.sons[ind].s)\n",
    "                node.sons[ind].s = \"\"\n",
    "            for row, col in [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:\n",
    "                if 0 <= row < m and 0 <= col < n:\n",
    "                    dfs(node.sons[ind], row, col)\n",
    "            visit[i][j] = 0\n",
    "            if not any(node.sons[ind].sons):\n",
    "                node.sons[ind] = None\n",
    "        \n",
    "        visit = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dfs(self.tree, i, j)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = dict()\n",
    "        self.is_word = False\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def insert(self, word):\n",
    "        node = self.root\n",
    "        for c in word:\n",
    "            if c not in node.children:\n",
    "                node.children[c] = TrieNode()\n",
    "            node = node.children[c]\n",
    "        node.is_word = True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            trie.insert(word)\n",
    "\n",
    "        m, n = len(board), len(board[0])\n",
    "        res = set()\n",
    "\n",
    "        def dfs(i, j, node=trie.root, word=\"\"):\n",
    "            if i < 0 or i == m or j < 0 or j == n or board[i][j] not in node.children:\n",
    "                return\n",
    "            node = node.children[board[i][j]]\n",
    "            word += board[i][j]\n",
    "            if node.is_word:\n",
    "                res.add(word)\n",
    "\n",
    "            board[i][j] = '#'\n",
    "            dfs(i + 1, j, node, word)\n",
    "            dfs(i - 1, j, node, word)\n",
    "            dfs(i, j + 1, node, word)\n",
    "            dfs(i, j - 1, node, word)\n",
    "            board[i][j] = word[-1]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dfs(i, j)\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.MAXN = 10001\n",
    "        self.tree = [[0]*26 for _ in range(self.MAXN)]\n",
    "        self.pass1 = [0] * self.MAXN\n",
    "        self.end = [None]*self.MAXN\n",
    "        self.cnt = 0\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "\n",
    "        \n",
    "        def build(words):\n",
    "          \n",
    "            self.cnt = 1\n",
    "            for word in words:\n",
    "                cur = 1\n",
    "                self.pass1[cur]+=1\n",
    "                for i in range(len(word)):\n",
    "                    path = ord(word[i])-ord('a')\n",
    "                    if self.tree[cur][path] == 0:\n",
    "                        self.cnt += 1\n",
    "                        self.tree[cur][path] = self.cnt\n",
    "                    cur = self.tree[cur][path]\n",
    "                    self.pass1[cur] += 1\n",
    "                self.end[cur] = word\n",
    "        def clear():\n",
    "       \n",
    "            for i in range(1,self.cnt+1):\n",
    "                self.tree[i] = [0 for i in range(len(self.tree[i]))]\n",
    "                self.pass1[i] = 0\n",
    "                self.end[i] = None\n",
    "        def dfs(board,i,j,t,ans):\n",
    "         \n",
    "            if i<0 or i==len(board) or j<0 or j==len(board[0]) or board[i][j]==0:\n",
    "                return 0\n",
    "            tmp = board[i][j]\n",
    "            road = ord(tmp)-ord('a')\n",
    "            t = self.tree[t][road]\n",
    "            if self.pass1[t] == 0:\n",
    "                return 0\n",
    "            fix = 0\n",
    "            if self.end[t]!=None:\n",
    "                fix+=1\n",
    "                ans.append(self.end[t])\n",
    "                self.end[t] = None\n",
    "            board[i][j] = 0\n",
    "            fix += dfs(board,i-1,j,t,ans)\n",
    "            fix += dfs(board,i+1,j,t,ans)\n",
    "            fix += dfs(board,i,j-1,t,ans)\n",
    "            fix += dfs(board,i,j+1,t,ans)\n",
    "            self.pass1[t] -= fix\n",
    "            board[i][j] = tmp\n",
    "            return fix\n",
    "        build(words)\n",
    "        ans = []\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                dfs(board,i,j,1,ans)\n",
    "        clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.next = defaultdict(Trie)\n",
    "        self.isEnd = False\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        p = self\n",
    "        for c in word:\n",
    "            if not p.next[c]:\n",
    "                p.next[c] = Trie()\n",
    "            p = p.next[c]\n",
    "        p.isEnd = True\n",
    "\n",
    "    def delete(self, word: str) -> None:\n",
    "        p = self\n",
    "        st = []\n",
    "        for c in word:\n",
    "            st.append((p, c))\n",
    "            p = p.next[c]\n",
    "        p.isEnd = False\n",
    "        if p.next:\n",
    "            # 还有子节点不删除\n",
    "            return\n",
    "        while st:\n",
    "            f, c = st.pop()\n",
    "            f.next.pop(c)\n",
    "            # 还有子节点的时候不能再向上追溯\n",
    "            if f.next:\n",
    "                break\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        p = self\n",
    "        for c in word:\n",
    "            p = p.next[c]\n",
    "            if not p:\n",
    "                return False\n",
    "        return p.isEnd\n",
    "\n",
    "    def startsWith(self, prefix: str) -> bool:\n",
    "        p = self\n",
    "        for c in prefix:\n",
    "            p = p.next[c]\n",
    "            if not p:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        ans = []\n",
    "        trie_root = Trie()\n",
    "        for w in words:\n",
    "            trie_root.insert(w)\n",
    "\n",
    "        def dfs(r, c, path: str, visit, node: Trie):\n",
    "            if r >= m or r < 0 or c >= n or c < 0 or visit[r][c] or not node or board[r][c] not in node.next:\n",
    "                return\n",
    "            visit[r][c] = True\n",
    "            ch = board[r][c]\n",
    "            path += ch\n",
    "            if node.next[ch].isEnd:\n",
    "                nonlocal ans\n",
    "                ans.append(path)\n",
    "                # print(r, c, path)\n",
    "                trie_root.delete(path)\n",
    "            for dr, dc in ((0, -1), (0, 1), (-1, 0), (1, 0)):\n",
    "                rr, cc = r+dr, c+dc\n",
    "                dfs(rr, cc, path, visit, node.next[ch])\n",
    "            visit[r][c] = False\n",
    "            path = path[:-1]\n",
    "        visit = [[False]*n for _ in range(m)]\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                dfs(r, c, '', visit, trie_root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = {}\n",
    "    def insert(self, word):\n",
    "        node = self.root\n",
    "        for ch in word+'#':\n",
    "            if ch not in node:\n",
    "                node[ch] = {}\n",
    "            node = node[ch]\n",
    "    def startswith(self, prefix):\n",
    "        node = self.root\n",
    "        for ch in prefix:\n",
    "            if ch not in node:\n",
    "                return False\n",
    "            node = node[ch]\n",
    "        return True\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        trie = Trie()\n",
    "        words = set(words)\n",
    "        for word in words:\n",
    "            trie.insert(word)\n",
    "        ans = set()\n",
    "        seen = set()\n",
    "        def dfs(i, j, strs):\n",
    "            if i<0 or j<0 or i>=len(board) or j>=len(board[0]):\n",
    "                return\n",
    "            if (i, j) in seen:\n",
    "                return\n",
    "            next_strs = strs+board[i][j]\n",
    "            if not trie.startswith(next_strs):\n",
    "                return\n",
    "            seen.add((i, j))\n",
    "            if next_strs in words:\n",
    "                ans.add(next_strs)\n",
    "            dfs(i+1, j, next_strs)\n",
    "            dfs(i-1, j, next_strs)\n",
    "            dfs(i, j+1, next_strs)\n",
    "            dfs(i, j-1, next_strs)\n",
    "            seen.remove((i, j))\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                before = len(ans)\n",
    "                dfs(i, j, '')\n",
    "                if len(ans) == before:\n",
    "                    continue\n",
    "                trie.root.clear()\n",
    "                words = words-ans\n",
    "                for word in words:\n",
    "                    trie.insert(word)\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.isWord = False\n",
    "        self.parent = -1\n",
    "        self.val = ''\n",
    "\n",
    "    def addWord(self, word):\n",
    "        cur = self\n",
    "        for c in word:\n",
    "            if c not in cur.children:\n",
    "                cur.children[c] = TrieNode()\n",
    "                cur.children[c].parent = cur\n",
    "                cur.children[c].val = c\n",
    "            cur = cur.children[c]\n",
    "        cur.isWord = True\n",
    "\n",
    "    def pruneWord(self):\n",
    "        cur = self\n",
    "        while len(cur.children) == 0 and cur.parent != -1:\n",
    "            par = cur.parent\n",
    "            del par.children[cur.val]\n",
    "            cur = par\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        root = TrieNode()\n",
    "        for w in words:\n",
    "            root.addWord(w)\n",
    "\n",
    "        rows, cols = len(board), len(board[0])\n",
    "        res, visit = set(), set()\n",
    "        directions = [[0,1],[0,-1], [1,0], [-1,0]]\n",
    "\n",
    "        def dfs(r,c, node, word):\n",
    "            if r < 0 or c < 0 or r==rows or c == cols or (r,c) in visit or board[r][c] not in node.children:\n",
    "                return \n",
    "\n",
    "            visit.add((r,c))\n",
    "            node = node.children[board[r][c]]\n",
    "            word += board[r][c]\n",
    "\n",
    "            if node.isWord:\n",
    "                res.add(word)\n",
    "                node.isWord = False\n",
    "                node.pruneWord()\n",
    "\n",
    "            for dr, dc in directions:\n",
    "                nr, nc = r + dr, c + dc\n",
    "                dfs(nr, nc, node, word)\n",
    "            visit.remove((r,c))\n",
    "\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                dfs(r, c, root, '')\n",
    "\n",
    "        return list(res)\n",
    "                        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.endOfWord = False\n",
    "        self.refs = 0\n",
    "\n",
    "    def addWord(self, word):\n",
    "        cur = self\n",
    "        cur.refs += 1\n",
    "        for c in word:\n",
    "            if c not in cur.children:\n",
    "                cur.children[c] = TrieNode()\n",
    "            cur = cur.children[c]\n",
    "            cur.refs += 1\n",
    "        cur.endOfWord = True\n",
    "    \n",
    "    def removeWord(self, word):\n",
    "        cur = self\n",
    "        cur.refs -= 1\n",
    "        for c in word:\n",
    "            if c in cur.children:\n",
    "                cur = cur.children[c]\n",
    "                cur.refs -= 1\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        def dfs(r, c, node, word, res, visited):\n",
    "            if r not in range(m) or c not in range(n) or board[r][c] not in node.children or node.children[board[r][c]].refs < 1 or (r, c) in visited:\n",
    "                return\n",
    "            visited.add((r, c))\n",
    "            print(board[r][c], 2)\n",
    "            node = node.children[board[r][c]]\n",
    "            word += board[r][c]\n",
    "            if node.endOfWord:\n",
    "                node.endOfWord = False\n",
    "                res.append(word)\n",
    "                root.removeWord(word)\n",
    "            \n",
    "            dfs(r+1, c, node, word, res, visited)\n",
    "            dfs(r-1, c, node, word, res, visited)\n",
    "            dfs(r, c+1, node, word, res, visited)\n",
    "            dfs(r, c-1, node, word, res, visited)\n",
    "            visited.remove((r, c))\n",
    "\n",
    "        root = TrieNode()\n",
    "        for w in words:\n",
    "            root.addWord(w)\n",
    "        \n",
    "        m, n = len(board), len(board[0])\n",
    "        res, visited = [], set()\n",
    "\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                print(board[r][c], 1)\n",
    "                dfs(r, c, root, \"\", res, visited)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        words = set(words)\n",
    "        ans = set()\n",
    "        visited = [[False] * len(board[0]) for _ in range(len(board))]\n",
    "\n",
    "        tree = Trie()\n",
    "        for word in words:\n",
    "            tree.insert(word)\n",
    "\n",
    "        def dfs(i, j, s):\n",
    "            if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or visited[i][j]:\n",
    "                return\n",
    "\n",
    "            s += board[i][j]\n",
    "            if s in words:\n",
    "                ans.add(s)\n",
    "                tree.remove(s)\n",
    "\n",
    "            if tree.startsWith(s):\n",
    "                visited[i][j] = True\n",
    "                dfs(i - 1, j, s)\n",
    "                dfs(i + 1, j, s)\n",
    "                dfs(i, j - 1, s)\n",
    "                dfs(i, j + 1, s)\n",
    "                visited[i][j] = False\n",
    "\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                dfs(i, j, \"\")\n",
    "\n",
    "        return list(ans)\n",
    "\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.pass_by = 0\n",
    "        self.end = 0\n",
    "        self.next = {}\n",
    "\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        self.root.pass_by += 1\n",
    "        node = self.root\n",
    "        for c in word:\n",
    "            if c not in node.next:\n",
    "                node.next[c] = TrieNode()\n",
    "            node.next[c].pass_by += 1\n",
    "            node = node.next[c]\n",
    "        node.end += 1\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        node = self.root\n",
    "        for c in word:\n",
    "            if c not in node.next:\n",
    "                return False\n",
    "            node = node.next[c]\n",
    "        return node.end > 0\n",
    "\n",
    "    def startsWith(self, prefix: str) -> bool:\n",
    "        node = self.root\n",
    "        for c in prefix:\n",
    "            if c not in node.next:\n",
    "                return False\n",
    "            node = node.next[c]\n",
    "        return True\n",
    "\n",
    "    def remove(self, word: str):\n",
    "        if not self.search(word):\n",
    "            return\n",
    "        node = self.root\n",
    "        for c in word:\n",
    "            if node.next[c].pass_by == 1:\n",
    "                node.next.pop(c)\n",
    "                return\n",
    "            node.next[c].pass_by -= 1\n",
    "            node = node.next[c]\n",
    "        node.end -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = collections.defaultdict(Trie)\n",
    "        self.word = ''\n",
    "    \n",
    "    def add(self, word):\n",
    "        cur = self\n",
    "        for ch in word:\n",
    "            cur = cur.children[ch]\n",
    "        cur.word = word\n",
    "    \n",
    "    def remove_word(self, word):\n",
    "        n = len(word)\n",
    "        def remove(trie, index):\n",
    "            if index == n:\n",
    "                trie.word = ''\n",
    "                if not trie.children:\n",
    "                    return None\n",
    "                else:\n",
    "                    return trie\n",
    "            \n",
    "            ch = word[index]\n",
    "            if ch not in trie.children:\n",
    "                return trie\n",
    "            nxt = remove(trie.children[ch], index + 1)\n",
    "            if not nxt:\n",
    "                del trie.children[ch]\n",
    "                if not trie.children and not trie.word:\n",
    "                    trie = None\n",
    "            return trie\n",
    "        remove(self, 0)\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        m, n = len(board), len(board[0])\n",
    "\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            trie.add(word)\n",
    "        \n",
    "        ans = []\n",
    "        visited = set()\n",
    "        def dfs(cur, x, y):\n",
    "            ch = board[x][y]\n",
    "            if ch not in cur.children:\n",
    "                return\n",
    "            cur = cur.children[ch]\n",
    "            visited.add((x, y))\n",
    "            if cur.word:\n",
    "                ans.append(cur.word)\n",
    "                trie.remove_word(cur.word)\n",
    "            for dx, dy in [(0,1), (0,-1), (1,0), (-1,0)]:\n",
    "                x0, y0 = x + dx, y + dy\n",
    "                if 0 <= x0 < m and 0 <= y0 < n and (x0, y0) not in visited:\n",
    "                    dfs(cur, x0, y0)\n",
    "            visited.remove((x,y))\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dfs(trie, i, j)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
